// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包解析为text/template 
// 和html/template定义的模板构建解析树。客户端应该使用这些包来构造模板
// 而不是此包，它提供的是共享的内部数据结构，而不是一般用途的
// 。
package parse

import (
	"bytes"
	"fmt"
	"runtime"
	"strconv"
	"strings"
)

// 树是单个已解析模板的表示形式。
type Tree struct {
	Name      string    // 由树表示的模板的名称。
	ParseName string    // 解析期间顶级模板的名称，用于错误消息。
	Root      *ListNode // 树的顶级根。
	Mode      Mode      // 解析模式。
	text      string    // 为创建模板（或其父级）而解析的文本
	// 仅解析；解析后清除。
	funcs      []map[string]interface{}
	lex        *lexer
	token      [3]item // 解析器的三个令牌前瞻。
	peekCount  int
	vars       []string // 目前定义的变量。
	treeSet    map[string]*Tree
	actionLine int // 左delim起始动作行
	mode       Mode
}

// 模式值是一组标志（或0）。模式控制解析器行为。
type Mode uint

const (
	ParseComments Mode = 1 << iota // 解析注释并将其添加到AST 
	SkipFuncCheck                  // 不检查是否定义了函数
)

// Copy返回树的副本。任何解析状态都将被丢弃。
func (t *Tree) Copy() *Tree {
	if t == nil {
		return nil
	}
	return &Tree{
		Name:      t.Name,
		ParseName: t.ParseName,
		Root:      t.Root.CopyList(),
		text:      t.text,
	}
}

// Parse返回模板名到Parse.Tree的映射，该映射是通过解析参数字符串中描述的
// 模板创建的。给定指定的名称，顶级模板将是
// 。如果遇到错误，解析将停止，并返回带有错误的空映射。
func Parse(name, text, leftDelim, rightDelim string, funcs ...map[string]interface{}) (map[string]*Tree, error) {
	treeSet := make(map[string]*Tree)
	t := New(name)
	t.text = text
	_, err := t.Parse(text, leftDelim, rightDelim, treeSet, funcs...)
	return treeSet, err
}

// next返回下一个令牌。
func (t *Tree) next() item {
	if t.peekCount > 0 {
		t.peekCount--
	} else {
		t.token[0] = t.lex.nextItem()
	}
	return t.token[t.peekCount]
}

// 备份将输入流向上备份一个令牌。
func (t *Tree) backup() {
	t.peekCount++
}

// backup2将输入流向上备份两个令牌。
// 第0个令牌已经存在。
func (t *Tree) backup2(t1 item) {
	t.token[1] = t1
	t.peekCount = 2
}

// backup3将输入流向上备份三个令牌
// 第零个令牌已经存在。
func (t *Tree) backup3(t2, t1 item) { // 相反顺序：我们在后退。
	t.token[1] = t1
	t.token[2] = t2
	t.peekCount = 3
}

// peek返回但不使用下一个令牌。
func (t *Tree) peek() item {
	if t.peekCount > 0 {
		return t.token[t.peekCount-1]
	}
	t.peekCount = 1
	t.token[0] = t.lex.nextItem()
	return t.token[0]
}

// nextNonSpace返回下一个非空间令牌。
func (t *Tree) nextNonSpace() (token item) {
	for {
		token = t.next()
		if token.typ != itemSpace {
			break
		}
	}
	return token
}

// PEEKNOSPACE返回但不使用下一个非空间令牌。
func (t *Tree) peekNonSpace() item {
	token := t.nextNonSpace()
	t.backup()
	return token
}

// 解析。

// New分配一个具有给定名称的新解析树。
func New(name string, funcs ...map[string]interface{}) *Tree {
	return &Tree{
		Name:  name,
		funcs: funcs,
	}
}

// ErrorContext返回输入文本中节点位置的文本表示形式。
// 接收器仅在节点没有指向内部树的指针时使用，
// 这可能在旧代码中出现。
func (t *Tree) ErrorContext(n Node) (location, context string) {
	pos := int(n.Position())
	tree := n.tree()
	if tree == nil {
		tree = t
	}
	text := tree.text[:pos]
	byteNum := strings.LastIndex(text, "\n")
	if byteNum == -1 {
		byteNum = pos // 在第一行。
	} else {
		byteNum++ // 换行后。
		byteNum = pos - byteNum
	}
	lineNum := 1 + strings.Count(text, "\n")
	context = n.String()
	return fmt.Sprintf("%s:%d:%d", tree.ParseName, lineNum, byteNum), context
}

// errorf格式化错误并终止处理。
func (t *Tree) errorf(format string, args ...interface{}) {
	t.Root = nil
	format = fmt.Sprintf("template: %s:%d: %s", t.ParseName, t.token[0].line, format)
	panic(fmt.Errorf(format, args...))
}

// 错误终止处理。
func (t *Tree) error(err error) {
	t.errorf("%s", err)
}

// expect使用下一个令牌并保证它具有所需的类型。
func (t *Tree) expect(expected itemType, context string) item {
	token := t.nextNonSpace()
	if token.typ != expected {
		t.unexpected(token, context)
	}
	return token
}

// expectOneOf使用下一个令牌并保证其具有所需类型之一。
func (t *Tree) expectOneOf(expected1, expected2 itemType, context string) item {
	token := t.nextNonSpace()
	if token.typ != expected1 && token.typ != expected2 {
		t.unexpected(token, context)
	}
	return token
}

// 意外投诉令牌并终止处理。
func (t *Tree) unexpected(token item, context string) {
	if token.typ == itemError {
		extra := ""
		if t.actionLine != 0 && t.actionLine != token.line {
			extra = fmt.Sprintf(" in action started at %s:%d", t.ParseName, t.actionLine)
			if strings.HasSuffix(token.val, " action") {
				extra = extra[len(" in action"):] // 避免“action in action”
			}
		}
		t.errorf("%s%s", token, extra)
	}
	t.errorf("unexpected %s in %s", token, context)
}

// recover是将恐慌从解析的顶层转换为返回的处理程序。
func (t *Tree) recover(errp *error) {
	e := recover()
	if e != nil {
		if _, ok := e.(runtime.Error); ok {
			panic(e)
		}
		if t != nil {
			t.lex.drain()
			t.stopParse()
		}
		*errp = e.(error)
	}
}

// startParse使用lexer初始化解析器。
func (t *Tree) startParse(funcs []map[string]interface{}, lex *lexer, treeSet map[string]*Tree) {
	t.Root = nil
	t.lex = lex
	t.vars = []string{"$"}
	t.funcs = funcs
	t.treeSet = treeSet
}

// Stopperse终止解析。
func (t *Tree) stopParse() {
	t.lex = nil
	t.vars = nil
	t.funcs = nil
	t.treeSet = nil
}

// Parse解析模板定义字符串以构造要执行的模板的表示形式。如果任一操作分隔符字符串为空，则使用
// default（“{”或“}}”）。嵌入的模板定义添加到
// 树集映射中。
func (t *Tree) Parse(text, leftDelim, rightDelim string, treeSet map[string]*Tree, funcs ...map[string]interface{}) (tree *Tree, err error) {
	defer t.recover(&err)
	t.ParseName = t.Name
	emitComment := t.Mode&ParseComments != 0
	t.startParse(funcs, lex(t.Name, text, leftDelim, rightDelim, emitComment), treeSet)
	t.text = text
	t.parse()
	t.add()
	t.stopParse()
	return t, nil
}

// 添加将树添加到t.treeSet。
func (t *Tree) add() {
	tree := t.treeSet[t.Name]
	if tree == nil || IsEmptyTree(tree.Root) {
		t.treeSet[t.Name] = t
		return
	}
	if !IsEmptyTree(t.Root) {
		t.errorf("template: multiple definition of template %q", t.Name)
	}
}

// IsEmptyTree报告此树（节点）是否除空格或注释外没有任何内容。
func IsEmptyTree(n Node) bool {
	switch n := n.(type) {
	case nil:
		return true
	case *ActionNode:
	case *CommentNode:
		return true
	case *IfNode:
	case *ListNode:
		for _, node := range n.Nodes {
			if !IsEmptyTree(node) {
				return false
			}
		}
		return true
	case *RangeNode:
	case *TemplateNode:
	case *TextNode:
		return len(bytes.TrimSpace(n.Text)) == 0
	case *WithNode:
	default:
		panic("unknown node: " + n.String())
	}
	return false
}

// parse是模板的顶级解析器，与itemList基本相同，只是它还解析{define}}操作。
// 它运行到EOF。
func (t *Tree) parse() {
	t.Root = t.newList(t.peek().pos)
	for t.peek().typ != itemEOF {
		if t.peek().typ == itemLeftDelim {
			delim := t.next()
			if t.nextNonSpace().typ == itemDefine {
				newT := New("definition") // 一旦我们知道，名称将被更新。
				newT.text = t.text
				newT.Mode = t.Mode
				newT.ParseName = t.ParseName
				newT.startParse(t.funcs, t.lex, t.treeSet)
				newT.parseDefinition()
				continue
			}
			t.backup2(delim)
		}
		switch n := t.textOrAction(); n.Type() {
		case nodeEnd, nodeElse:
			t.errorf("unexpected %s", n)
		default:
			t.Root.append(n)
		}
	}
}

// parseDefinition解析一个{define}}。。。{{end}}模板定义和
// 在t.treeSet中安装该定义。“define”关键字已被扫描。
func (t *Tree) parseDefinition() {
	const context = "define clause"
	name := t.expectOneOf(itemString, itemRawString, context)
	var err error
	t.Name, err = strconv.Unquote(name.val)
	if err != nil {
		t.error(err)
	}
	t.expect(itemRightDelim, context)
	var end Node
	t.Root, end = t.itemList()
	if end.Type() != nodeEnd {
		t.errorf("unexpected %s in %s", end, context)
	}
	t.add()
	t.stopParse()
}

// itemList:
// textOrAction*
// 终止于{end}或{else}，单独返回。
func (t *Tree) itemList() (list *ListNode, next Node) {
	list = t.newList(t.peekNonSpace().pos)
	for t.peekNonSpace().typ != itemEOF {
		n := t.textOrAction()
		switch n.Type() {
		case nodeEnd, nodeElse:
			return list, n
		}
		list.append(n)
	}
	t.errorf("unexpected EOF")
	return
}

// text操作：
// text | comment | action 
func (t *Tree) textOrAction() Node {
	switch token := t.nextNonSpace(); token.typ {
	case itemText:
		return t.newText(token.pos, token.val)
	case itemLeftDelim:
		t.actionLine = token.line
		defer t.clearActionLine()
		return t.action()
	case itemComment:
		return t.newComment(token.pos, token.val)
	default:
		t.unexpected(token, "input")
	}
	return nil
}

func (t *Tree) clearActionLine() {
	t.actionLine = 0
}

// 操作：
// 控制
// 命令（“|”命令）*
// 左delim已过。现在开始行动。
// 第一个单词可以是关键字，如range。
func (t *Tree) action() (n Node) {
	switch token := t.nextNonSpace(); token.typ {
	case itemBlock:
		return t.blockControl()
	case itemElse:
		return t.elseControl()
	case itemEnd:
		return t.endControl()
	case itemIf:
		return t.ifControl()
	case itemRange:
		return t.rangeControl()
	case itemTemplate:
		return t.templateControl()
	case itemWith:
		return t.withControl()
	}
	t.backup()
	token := t.peek()
	// 不要弹出变量；它们一直持续到“结束”。
	return t.newAction(token.pos, token.line, t.pipeline("command", itemRightDelim))
}

// 管道：
// 声明？命令（“|”命令）*
func (t *Tree) pipeline(context string, end itemType) (pipe *PipeNode) {
	token := t.peekNonSpace()
	pipe = t.newPipeline(token.pos, token.line, nil)
	// 是否有声明或赋值？
decls:
	if v := t.peekNonSpace(); v.typ == itemVariable {
		t.next()
		// 因为空间是一个令牌，所以在最坏的情况下我们需要3-token向前看：
		// 在“$x foo”中，我们需要读“foo”（而不是“：”），才能知道$x是一个
		// 参数变量，而不是一个声明。因此，请记住变量旁边的标记
		// 以便在必要时将其推回。
		tokenAfterVariable := t.peek()
		next := t.peekNonSpace()
		switch {
		case next.typ == itemAssign, next.typ == itemDeclare:
			pipe.IsAssign = next.typ == itemAssign
			t.nextNonSpace()
			pipe.Decl = append(pipe.Decl, t.newVariable(v.pos, v.val))
			t.vars = append(t.vars, v.val)
		case next.typ == itemChar && next.val == ",":
			t.nextNonSpace()
			pipe.Decl = append(pipe.Decl, t.newVariable(v.pos, v.val))
			t.vars = append(t.vars, v.val)
			if context == "range" && len(pipe.Decl) < 2 {
				switch t.peekNonSpace().typ {
				case itemVariable, itemRightDelim, itemRightParen:
					// 范围管道中的第二个初始化变量
					goto decls
				default:
					t.errorf("range can only initialize variables")
				}
			}
			t.errorf("too many declarations in %s", context)
		case tokenAfterVariable.typ == itemSpace:
			t.backup3(v, tokenAfterVariable)
		default:
			t.backup2(v)
		}
	}
	for {
		switch token := t.nextNonSpace(); token.typ {
		case end:
			// 此时，管道已完成
			t.checkPipeline(pipe, context)
			return
		case itemBool, itemCharConstant, itemComplex, itemDot, itemField, itemIdentifier,
			itemNumber, itemNil, itemRawString, itemString, itemVariable, itemLeftParen:
			t.backup()
			pipe.append(t.command())
		default:
			t.unexpected(token, context)
		}
	}
}

func (t *Tree) checkPipeline(pipe *PipeNode, context string) {
	// 拒绝空管道
	if len(pipe.Cmds) == 0 {
		t.errorf("missing value for %s", context)
	}
	// 只有管道的第一个命令可以以不可执行的操作数
	for i, c := range pipe.Cmds[1:] {
		switch c.Args[0].Type() {
		case NodeBool, NodeDot, NodeNil, NodeNumber, NodeString:
			// 以a | B | C开头，管道第2阶段为B 
			t.errorf("non executable command in pipeline stage %d", i+2)
		}
	}
}

func (t *Tree) parseControl(allowElseIf bool, context string) (pos Pos, line int, pipe *PipeNode, list, elseList *ListNode) {
	defer t.popVars(len(t.vars))
	pipe = t.pipeline(context, itemRightDelim)
	var next Node
	list, next = t.itemList()
	switch next.Type() {
	case nodeEnd: // 完成
	case nodeElse:
		if allowElseIf {
			// 特殊情况为“else if”。如果“else”后面紧接着一个“If”，则
			// elseControl将使“If”标记挂起。将
			// /{{if a}}{{else if b}}}{{end}}
			// 视为
			// /{if a}{else}{{else b}{end}{end}}{。
			// 要执行此操作，请像往常一样解析if并在它{{end}处停止；假定后面的{end}
			// 为空。这种技术即使在长时间的if-else-if链中也有效。
			// TODO:如果在范围内，我们是否应该允许其他人？
			if t.peek().typ == itemIf {
				t.next() // 使用“如果”标记。
				elseList = t.newList(next.Position())
				elseList.append(t.ifControl())
				// 不要使用下一项-只需要一个{end}}。
				break
			}
		}
		elseList, next = t.itemList()
		if next.Type() != nodeEnd {
			t.errorf("expected end; found %s", next)
		}
	}
	return pipe.Position(), pipe.Line, pipe, list, elseList
}

// If:
// /{{If pipeline}}项目列表{{end}}
// /{{If pipeline}项目列表{else}项目列表{{end}}}
// If关键字已过。
func (t *Tree) ifControl() Node {
	return t.newIf(t.parseControl(true, "if"))
}

// 范围：
// /{{Range pipeline}}项目列表{{end}}
// /{{Range pipeline}}项目列表{else}}项目列表{end}}
// 范围关键字已过。
func (t *Tree) rangeControl() Node {
	return t.newRange(t.parseControl(false, "range"))
}

// With:
// /{{With pipeline}}项目列表{{end}}
// /{{{With pipeline}}项目列表{else}}项目列表{end}}
// /如果关键字已过。
func (t *Tree) withControl() Node {
	return t.newWith(t.parseControl(false, "with"))
}

// End:
// {End}}
// End关键字已过。
func (t *Tree) endControl() Node {
	return t.newEnd(t.expect(itemRightDelim, "end").pos)
}

// /Else:
// {Else}
// /Else关键字已过。
func (t *Tree) elseControl() Node {
	// “如果”的特殊情况。
	peek := t.peekNonSpace()
	if peek.typ == itemIf {
		// 我们看到“{else if…”但实际上将其重写为{{else}{{if…”
		return t.newElse(peek.pos, peek.line)
	}
	token := t.expect(itemRightDelim, "else")
	return t.newElse(token.pos, token.line)
}

// Block关键字已过。
// 名称必须是可以计算为字符串的内容。
// 管道是必需的。
func (t *Tree) blockControl() Node {
	const context = "block clause"

	token := t.nextNonSpace()
	name := t.parseTemplateName(token, context)
	pipe := t.pipeline(context, itemRightDelim)

	block := New(name) // 名称将在我们知道后更新。
	block.text = t.text
	block.Mode = t.Mode
	block.ParseName = t.ParseName
	block.startParse(t.funcs, t.lex, t.treeSet)
	var end Node
	block.Root, end = block.itemList()
	if end.Type() != nodeEnd {
		t.errorf("unexpected %s in %s", end, context)
	}
	block.add()
	block.stopParse()

	return t.newTemplate(token.pos, token.line, name, pipe)
}

// 模板：
// /{模板stringValue管道}
// 模板关键字已过。名称必须是可以将
// 计算为字符串的名称。
func (t *Tree) templateControl() Node {
	const context = "template clause"
	token := t.nextNonSpace()
	name := t.parseTemplateName(token, context)
	var pipe *PipeNode
	if t.nextNonSpace().typ != itemRightDelim {
		t.backup()
		// 不要弹出变量；它们会一直保留到“end”。
		pipe = t.pipeline(context, itemRightDelim)
	}
	return t.newTemplate(token.pos, token.line, name, pipe)
}

func (t *Tree) parseTemplateName(token item, context string) (name string) {
	switch token.typ {
	case itemString, itemRawString:
		s, err := strconv.Unquote(token.val)
		if err != nil {
			t.error(err)
		}
		name = s
	default:
		t.unexpected(token, context)
	}
	return
}

// 命令：
// 操作数（空格操作数）*
// 以空格分隔的参数，最多使用管道字符或右分隔符。
// 我们使用管道字符，但保留终止操作的权限。
func (t *Tree) command() *CommandNode {
	cmd := t.newCommand(t.peekNonSpace().pos)
	for {
		t.peekNonSpace() // 跳过前导空格。
		operand := t.operand()
		if operand != nil {
			cmd.append(operand)
		}
		switch token := t.next(); token.typ {
		case itemSpace:
			continue
		case itemRightDelim, itemRightParen:
			t.backup()
		case itemPipe:
			// 此处无任何内容；
		default:
			t.unexpected(token, "operand")
		}
		break
	}
	if len(cmd.Args) == 0 {
		t.errorf("empty command")
	}
	return cmd
}

// 操作数：
// term.Field*
// 操作数是命令中以空格分隔的组件，
// 一个可能后跟字段访问的术语。
// 零返回表示下一项不是操作数。
func (t *Tree) operand() Node {
	node := t.term()
	if node == nil {
		return nil
	}
	if t.peek().typ == itemField {
		chain := t.newChain(t.peek().pos, node)
		for t.peek().typ == itemField {
			chain.Add(t.next().val)
		}
		// 与原始API的兼容性：如果该术语的类型为NodeField 
		// 或NodeVariable，只需在原始文件上添加更多字段。
		// 否则，保留链节点。
		// 此处检测到涉及文字值的明显解析错误。
		// 执行时将必须处理更复杂的错误情况。
		switch node.Type() {
		case NodeField:
			node = t.newField(chain.Position(), chain.String())
		case NodeVariable:
			node = t.newVariable(chain.Position(), chain.String())
		case NodeBool, NodeString, NodeNumber, NodeNil, NodeDot:
			t.errorf("unexpected . after term %q", node.String())
		default:
			node = chain
		}
	}
	return node
}

// 术语：
// 文字（数字、字符串、零、布尔）
// function（identifier）
// .
// .Field 
// $
// '（'pipeline'）
// /一个术语是一个简单的“表达式”".
// nil返回表示下一项不是术语。
func (t *Tree) term() Node {
	switch token := t.nextNonSpace(); token.typ {
	case itemIdentifier:
		checkFunc := t.Mode&SkipFuncCheck == 0
		if checkFunc && !t.hasFunction(token.val) {
			t.errorf("function %q not defined", token.val)
		}
		return NewIdentifier(token.val).SetTree(t).SetPos(token.pos)
	case itemDot:
		return t.newDot(token.pos)
	case itemNil:
		return t.newNil(token.pos)
	case itemVariable:
		return t.useVar(token.pos, token.val)
	case itemField:
		return t.newField(token.pos, token.val)
	case itemBool:
		return t.newBool(token.pos, token.val == "true")
	case itemCharConstant, itemComplex, itemNumber:
		number, err := t.newNumber(token.pos, token.val, token.typ)
		if err != nil {
			t.error(err)
		}
		return number
	case itemLeftParen:
		return t.pipeline("parenthesized pipeline", itemRightParen)
	case itemString, itemRawString:
		s, err := strconv.Unquote(token.val)
		if err != nil {
			t.error(err)
		}
		return t.newString(token.pos, token.val, s)
	}
	t.backup()
	return nil
}

// hasFunction报告树的映射中是否存在函数名。
func (t *Tree) hasFunction(name string) bool {
	for _, funcMap := range t.funcs {
		if funcMap == nil {
			continue
		}
		if funcMap[name] != nil {
			return true
		}
	}
	return false
}

// popVars将变量列表修剪为指定长度
func (t *Tree) popVars(n int) {
	t.vars = t.vars[:n]
}

// useVar为变量引用返回一个节点。如果
// 变量为未定义。
func (t *Tree) useVar(pos Pos, name string) Node {
	v := t.newVariable(pos, name)
	for _, varName := range t.vars {
		if varName == v.Ident[0] {
			return v
		}
	}
	t.errorf("undefined variable %q", v.Ident[0])
	return nil
}
